package com.ufpb.algoritmosEstrutura.arvoreGeradoraMinima;

public class ConjuntosDisjuntos {
	private int cnt;
	private int pai[];
	private int sz[];
	
	public ConjuntosDisjuntos(int n){
		cnt=n;
		this.pai=new int[n];
		this.sz= new int[n];
		for(int i=0;i<n;i++){
			pai[i]=i;
		}
		for(int i=0;i<n;i++){
			sz[i]=1;
		}
	}
	public int ache(int x){
		if(x!=pai[x]){
			pai[x]=ache(pai[x]);
		}
		return pai[x];
	}
	public void uniao(int x,int y){
		int i=ache(x);
		int j=ache(y);
		
		if(pai[i]==pai[j]){
			return;
		}
		if(sz[i]<sz[j]){
			pai[i]=j;
			pai[j]=sz[j]+sz[i];
		}
		else{
			pai[j]=i;
			sz[i]=sz[i]+sz[j];
		}
		cnt=cnt-1;
	}
}